package sort;


import javax.xml.stream.FactoryConfigurationError;
import java.text.BreakIterator;
import java.util.Arrays;
import java.util.Random;

public class Sort {
    public static void main(String[] args) {
        int[] arr = {3, 9, 0, -2, 1};


        System.out.println("排序前=" + Arrays.toString(arr));
        Sort sort = new Sort();
        //冒泡排序
//        sort.bubble(arr);

        //选择排序
//        sort.select(arr);

        //插入排序
//        sort.insert(arr);

        //希尔排序 交换法
//        sort.shell(arr);

        //希尔排序 移位法
//        sort.shell2(arr);

        //(随机)快速排序
        sort.randomizedQuicksort(arr,0,arr.length-1);

    }


    /**
     * 随机快排
     * 快速排序，一种优化的冒泡排序
     * 找一个基准值，把比他小的放到左边，比他大的放到右边
     * 然后对两边进行递归。
     *
     * @param
     */
    public void randomizedQuicksort(int[] nums, int l, int r) {
        if (l < r) {
            int pos = randomizedPartition(nums, l, r);
            randomizedQuicksort(nums, l, pos - 1);
            randomizedQuicksort(nums, pos + 1, r);
        }
        System.out.println(Arrays.toString(nums));
    }

    public int randomizedPartition(int[] nums, int l, int r) {
        int i = new Random().nextInt(r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums, r, i);
        return partition(nums, l, r);
    }

    public int partition(int[] nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, r);
        return i + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }





    /**
     * 希尔排序 移位法
     * 移动的时候是和插入排序的思想一样
     *
     * @param arr
     */
    private void shell2(int[] arr) {

        //增量gap，并逐步的缩小增量
        for (int gap = arr.length; gap > 0; gap /= 2) {

            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];

                if (arr[j] < arr[j - gap]) {
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        //移动，
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    arr[j] = temp;
                }
            }

        }

        System.out.println("希尔排序后=" + Arrays.toString(arr));
    }

    /**
     * 希尔排序 交换法
     * 发现之后交换位置
     * 优化的直接插入排序
     * 每次都把集合进行分组，每组都进行直接插入排序
     * 首先分为 arr = arr.length / 2 组，并且每组进行直接排序
     * 然后一直循环
     *
     * @param arr
     */
    private void shell(int[] arr) {

        int temp = 0;

        //增量gap，并逐步的缩小增量
        for (int gap = arr.length; gap > 0; gap /= 2) {

            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }

        }

        System.out.println("希尔排序后=" + Arrays.toString(arr));
    }


    /**
     * 插入排序
     * 把集合分为有序集合和无序集合，
     * 每次循环都把一个无序集合中的一个元素放置到有序集合中的正确位置。
     *
     * @param arr
     */
    private void insert(int[] arr) {

        for (int i = 1; i < arr.length; i++) {
            int val = arr[i];
            int index = i - 1;
            while (index >= 0 && val < arr[index]) {
                arr[index + 1] = arr[index];
                index--;
            }
            arr[index + 1] = val;
        }

        System.out.println("插入排序后=" + Arrays.toString(arr));
    }

    /**
     * 选择排序（升序）
     * 每次循环都会找到剩余元素中最小的一个元素，并放置到相应的位置。
     *
     * @param arr
     */
    private void select(int[] arr) {
        int min = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            if (min != i) {
                int t = arr[i];
                arr[i] = arr[min];
                arr[min] = t;
            }

        }
        System.out.println("选择排序后=" + Arrays.toString(arr));
    }


    /**
     * 冒泡排序（升序）
     * 每次循环把剩余元素中最大的元素移动到剩余集合的最后一个位置
     * 每次都找到当前集合的最大值。
     *
     * @param arr
     */
    private void bubble(int[] arr) {
        int temp = 0;
        boolean flag = false;//标志位，判断有没有进行交换，如果没有，则可以提前结束循环。
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            if (!flag) {
                break;
            } else {
                flag = false;
            }
        }
        System.out.println("冒泡排序后=" + Arrays.toString(arr));
    }

}
